#include<iostream>
#include<sstream>
#include "List.h"
using namespace std;

List::List() {
	pHead = NULL;
	count = 0;
}

int List::size() {
	if (pHead == NULL)
		return 0;
	else {
		int size = 0;
		Node *pt = pHead;
		while (pt != NULL) {
			size++;
			pt = pt->next;
		}
		return size;
	}
}

Node* List::getHead() {
	return pHead;
}

Node* List::getLast() {
	if (pHead == NULL)
		return NULL;
	else if (pHead->next == NULL)
		return pHead;
	else {
		Node* ptr = pHead;
		while (ptr->next != NULL)
			ptr = ptr->next;
		return ptr;
	}
}

void List::setHead(Node* head) {
	if (pHead == NULL)
		pHead = head;
	else {
		head->next = pHead;
		pHead = head;
	}
}

void List::addFirst(int newdata) {
	Node* pTemp = new Node;
	pTemp->data = newdata;
	pTemp->next = pHead;
	pHead = pTemp;
	count++;
}

void List::addLast(int newData) {
	Node *newNode = new Node;
	newNode->data = newData;
	newNode->next = NULL;
	if (pHead == NULL)
		pHead = newNode;
	else {
		Node *pt = pHead;
		while (pt->next != NULL)
			pt = pt->next;
		pt->next = newNode;
	}
}

void List::clear() {
	while (!empty())
		removeFirst();
	return;
}

void List::display() {
	if (pHead == NULL) {
		cout << "List is null";
		return;
	}

	Node *pt = pHead;
	while (pt != NULL) {
		if (pt->next == NULL)
			cout << pt->data << " -> NULL " << endl;
		else
			cout << pt->data << " -> ";
		pt = pt->next;
	}
}

void List::addConstant(int nConstant) {
	return;
}

int List::empty() {
	return (pHead == NULL);
}

void List::removeFirst() {
	if (pHead != NULL) {
		Node* pTemp = pHead;
		pHead = pHead->next;
		delete pTemp;
		count--;
	}
	return;
}

/*
 * Some convert function
 */
string int_to_string(const int& port) {
	stringstream ss;
	ss << port;
	return ss.str();
}

int string_to_int(string str) {
	stringstream ss(str);
	int value = 0;
	ss >> value;
	return value;
}

List* List::buildPosLinkedList() {

	List* aList = new List;
	string num;
	int valid = 1;
	char choice;

	while (valid) {
		cout << "Add to list(Y/N) ? ";
		cin >> choice;
		cin.ignore();
		if (choice == 'y' || choice == 'Y') {
			cin.ignore();
			while (true) {
				cout << "Add Value : ";
				getline(cin, num);
				if (num.compare("n") == 0 || num.compare("N") == 0) {
					valid = 0;
					break;
				} else {
					int val = string_to_int(num);
					if (val > 0)
						aList->addLast(val);
				}
			}
		} else
			valid = 0;
	}
	return aList;
}

List* List::buildLinkedList() {
	List* aList = new List();
	int num;
	int valid = 1;
	char choice;

	while (valid) {
		cout << "Add (Y/N) ? ";
		cin >> choice;
		cin.ignore();
		if (choice == 'y' || choice == 'Y') {
			cout << "Value : ";
			cin >> num;
			aList->addLast(num);
		} else
			valid = 0;
	}
	return aList;

}

bool isFiboNumber(int n) {
	int a = 1;
	int b = 1;
	int c = a + b;
	while (c <= n) {
		if (c == n)
			return true;
		else {
			a = b;
			b = c;
			c = a + b;
		}
	}
	return false;
}
void List::addFiboNumber(int fiboNum) {
	if (isFiboNumber(fiboNum))
		addLast(fiboNum);
}

void List::addPos(int data, int index) {
	if (index == 0)
		addFirst(data);
	else if (index == (size() - 1))
		addLast(data);
	else {
		Node *node = new Node;
		node->data = data;
		node->next = NULL;
		Node *pt = pHead;
		int c = 0;
		while (c < (index - 1)) {
			pt = pt->next;
			c++;
		}

		node->next = pt->next;
		pt->next = node;
	}
}

string List::getElemByPos(int index) {
	if (index == 0) {
		int val = pHead->data;
		string rs = int_to_string(val);
		return rs;
	} else if (index >= size())
		return "No Element";
	else {
		int c = 0;
		Node *pt = pHead;
		while (c < index) {
			pt = pt->next;
			c++;
		}
		int val = pt->data;
		string rs = int_to_string(val);
		return rs;
	}
}

bool List::isExist(int elem) {
	Node *pt = pHead;
	while (pt != NULL) {
		if (pt->data == elem)
			return true;
		pt = pt->next;
	}
	return false;
}

void List::reverse() {
	if (pHead == NULL)
		return;
	else {
		int listSize = size();
		Node *pt = pHead;
		Node *ptN = pt->next;
		int c = 2;
		while (c <= listSize) {
			addFirst(ptN->data);
			pt->next = ptN->next;
			delete ptN;
			ptN = pt->next;
			c++;
		}
	}
}

void List::sort() {

	//convert list to array
	int SIZE = size();
	int arr[SIZE];
	int i = 0;
	Node* pt = pHead;
	while (pt != NULL) {
		arr[i++] = pt->data;
		pt = pt->next;
	}

	//sort array
	for (int i = 0; i < SIZE - 1; i++)
		for (int j = i + 1; j < SIZE; j++) {
			if (arr[i] > arr[j]) {
				int tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
			}
		}

	//convert sorted array to list
	this->~List();
	for (int i = 0; i < SIZE; i++)
		addLast(arr[i]);
}

void List::mergeSortedList(List *a, List *b) {
	Node *bPtr = b->getHead();
	while (bPtr != NULL) {
		if (bPtr->data <= a->getHead()->data)
			a->addFirst(bPtr->data);
		else if (bPtr->data >= a->getLast()->data)
			a->addLast(bPtr->data);
		else {
			Node* aPtr = a->getHead();
			while (aPtr->next->data < bPtr->data)
				aPtr = aPtr->next;
			Node* aPtNext = aPtr->next;
			Node* pNew = new Node;
			pNew->next = aPtNext;
			pNew->data = bPtr->data;
			aPtr->next = pNew;
		}
		bPtr = bPtr->next;
	}

	b->~List();
}

void List::getIntersection(List* aList, List* bList) {
	clear();
	Node* aTemp = aList->getHead();
	while (aTemp != NULL) {
		Node* bTemp = bList->getHead();
		while (bTemp != NULL) {
			if (bTemp->data == aTemp->data && !isExist(bTemp->data))
				addLast(aTemp->data);
			bTemp = bTemp->next;
		}

		aTemp = aTemp->next;
	}
}

void List::getUnion(List* aList, List* bList) {
	clear();
	Node* aTemp = aList->getHead();

	while (aTemp != NULL) {
		addLast(aTemp->data);
		aTemp = aTemp->next;
	}
	Node* bTemp = bList->getHead();
	while (bTemp != NULL) {
		if (!isExist(bTemp->data))
			addLast(bTemp->data);
		bTemp = bTemp->next;
	}
}
/*
 * 	For Polynomials Evaluations
 */
void List::addPoly(List *f2) {
	return;
}

void List::printPoly() {
	return;
}

List::~List() {
	Node* pTemp = pHead;
	while (pTemp != NULL) {
		pTemp = pTemp->next;
		delete pHead;
		pHead = pTemp;
	}
}

/*
 *
 *
 *
 *
 *
 *
 */
